package solutions;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-28
 * Time: 12:47
 */

//https://leetcode.cn/problems/merge-sorted-array/description/
class Solution3 {
    //逆序插入
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int idx1 = m - 1;
        int idx2 = n - 1;
        int idx3 = m + n - 1;
        while (idx1 >= 0 && idx2 >= 0) {
            if (nums1[idx1] >= nums2[idx2]) {
                nums1[idx3] = nums1[idx1];
                idx1--;
                idx3--;
            } else {
                nums1[idx3] = nums2[idx2];
                idx2--;
                idx3--;
            }
        }
        //nums1顺序有序，所以只需考虑nums2是否已经全部排列完毕
        while (idx3 >= 0 && idx2 >= 0) {
            nums1[idx3--] = nums2[idx2--];
        }
    }
}
